Temperature 1 Self-Assembly: Deterministic Assembly in 3D and Probabilistic Assembly in 2D

摘要

We investigate the power of the Wang tile self-assembly model at temperature1, a threshold value that permits attachment between any two tiles that shareeven a single bond. When restricted to deterministic assembly in the plane, notemperature 1 assembly system has been shown to build a shape with a tilecomplexity smaller than the diameter of the shape. In contrast, we show thattemperature 1 self-assembly in 3 dimensions, even when growth is restricted toat most 1 step into the third dimension, is capable of simulating a large classof temperature 2 systems, in turn permitting the simulation of arbitrary Turingmachines and the assembly of $n\times n$ squares in near optimal $O(\log n)$tile complexity. Further, we consider temperature 1 probabilistic assembly in2D, and show that with a logarithmic scale up of tile complexity and shapescale, the same general class of temperature $\tau=2$ systems can be simulatedwith high probability, yielding Turing machine simulation and $O(\log^2 n)$assembly of $n\times n$ squares with high probability. Our results show a sharpcontrast in achievable tile complexity at temperature 1 if either growth intothe third dimension or a small probability of error are permitted. Motivated byapplications in nanotechnology and molecular computing, and the plausibility ofimplementing 3 dimensional self-assembly systems, our techniques may providethe needed power of temperature 2 systems, while at the same time avoiding theexperimental challenges faced by those systems.